# -*- coding: utf-8 -*-

"""剑指 Offer II 094. 最少回文分割
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。

示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：
输入：s = "a"
输出：0

示例 3：
输入：s = "ab"
输出：1

提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成"""


class Solution:
    """到第 i 位时，以 s[i] 为结尾的回文子串开头有 a, b, c，那么可分割的次数最少为
    以 a-1, b-1, c-1 为结尾的字符串最少分割次数 +1
    状态转移方程为：
    f(i) = min(f(a-1), f(b-1), f(c-1)) +1
    
    考虑到len(s) <= 2000，如果全是a-z的单调循环，就要挨个来，用递归可能造成栈溢出；
    应该先计算出，以i为结尾的所有回文字符串；
    初始dp，默认挨个分割，dp[i] = i"""
    def minCut(self, s: str) -> int:
        def generate_palindromes(s):
            s, palins = ','.join(s), dict((i, set()) for i in range(len(s)))
            hi = len(s)
            for middle in range(hi):
                left, right = middle, middle
                while left >= 0 and right < hi:
                    if s[left] != s[right]:
                        break
                    if s[left] != ',' and s[left] == s[right]:
                        palins[right//2].add(left//2)
                    left -= 1
                    right += 1
            return palins
        
        dp, palins = list(range(len(s))), generate_palindromes(s)

        for i in range(len(s)):
            for a in palins[i]:
                if a-1 < 0:
                    dp[i] = min(0, dp[i])
                else:
                    dp[i] = min(dp[a-1]+1, dp[i])
        return dp[len(s)-1]


if __name__ == '__main__':
    so = Solution()
    print(so.minCut("aab"))
    print(so.minCut("a"))
    print(so.minCut("ab"))
    print(so.minCut("cabababcbc"))
